27. Remove Element

Solution 1: Two Pointer + Swap

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        if len(nums) == 1:
            return 1 if val != nums[0] else 0
        
        i = 0
        j = len(nums) - 1
        while i < j:
            # Find the removable element from left
            while i < len(nums) and nums[i] != val:
                i += 1
            # Find the proper element from right
            while j > 0 and nums[j] == val:
                j -= 1
            
            # If the index haven't cross, swap
            if i < j:
                nums[i], nums[j] = nums[j], nums[i]
        return i

Time Complexity: O(N)
Space Complexity: O(1)

Solution 2: Two Pointer

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        k = 0
        for idx in range(len(nums)):
            if nums[idx] != val:
                nums[k] = nums[idx]
                k += 1
        return k

Time Complexity: O(N)
Space Complexity: O(1)

Reference

https://leetcode.com/problems/remove-element/discuss/2785400/C%2B%2B-oror-Faster-than-100-oror-Two-pointer-oror-Simple-Code-oror

Follow-up: Remove Duplicates from Sorted Array

Follow-up: Remove Linked List Elements

Follow-up: Move Zeroes